import java.util.*;

public class project {
    public int numSplits(String s) {
        Map<Character,Integer> left=new HashMap<>();
        Map<Character,Integer> right=new HashMap<>();
        int len=s.length();
        left.put(s.charAt(0),1);
        int ret=0;
        for(int i=1;i<len;i++){
            right.put(s.charAt(i),right.getOrDefault(s.charAt(i),0)+1);
        }
        if(left.size()==right.size()){
            ret++;
        }
        for(int i=1;i<len-1;i++){
            char ch=s.charAt(i);
            left.put(ch,left.getOrDefault(ch,0)+1);
            if(right.get(ch)-1==0){
                right.remove(ch);
            }else{
                right.put(ch,right.get(ch)-1);
            }
            if(left.size()==right.size()){
                ret++;
            }
        }
        return ret;
    }


















    public int kthLargestValue(int[][] matrix, int k) {
        int row=matrix.length;
        int col=matrix[0].length;
        int[][] dp=new int[row+1][col+1];
        List<Integer> list=new ArrayList<>();
        for(int i=1;i<=row;i++){
            for(int j=1;j<=col;j++){
                dp[i][j]=dp[i-1][j]^dp[i][j-1]^dp[i-1][j-1]^matrix[i-1][j-1];
                list.add(dp[i][j]);
            }
        }
        Collections.sort(list);
        return list.get(list.size()-k);
    }















    public List<List<String>> displayTable(List<List<String>> orders) {
        Map<Integer,Map<String,Integer>> map=new HashMap<>();
        Set<String> foods=new HashSet<>();
        for(List<String> list:orders){
            int table=Integer.parseInt(list.get(1));
            String food=list.get(2);
            Map<String,Integer> value=map.getOrDefault(table,new HashMap<>());
            value.put(food,value.getOrDefault(food,0)+1);
            map.put(table,value);
            foods.add(food);
        }

        int foodLen=foods.size();
        List<String> foodName=new ArrayList<>();
        for(String s:foods){
            foodName.add(s);
        }
        Collections.sort(foodName);


        int tableLen=map.size();
        List<Integer> tableId=new ArrayList<>();
        for(int id:map.keySet()){
            tableId.add(id);
        }
        Collections.sort(tableId);

        List<List<String>> ret=new ArrayList<>();
        List<String> head=new ArrayList<>();
        head.add("Table");
        for(String name: foodName){
            head.add(name);
        }
        ret.add(head);
        for(int i=0;i<tableLen;i++){
            int id=tableId.get(i);
            Map<String,Integer> table=map.get(id);
            List<String> value=new ArrayList<>();
            value.add(String.valueOf(id));
            for(int j=0;j<foodLen;j++){
                value.add(String.valueOf(table.getOrDefault(foodName.get(j),0)));
            }
            ret.add(value);
        }
        return ret;
    }





















    public List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        Set<Integer> set=new HashSet<>();
        List<Integer> list=new ArrayList<>();
        for(List<Integer> edge:edges){
            set.add(edge.get(1));
        }
        for(int i=0;i<n;i++){
            if(!set.contains(i)){
                list.add(i);
            }
        }
        return list;
    }

















    public String[] reorderLogFiles(String[] logs) {
        Arrays.sort(logs,(logs1,logs2)->{
            String[] str1=logs1.split(" ",2);
            String[] str2=logs2.split(" ",2);
            boolean flag1=Character.isDigit(str1[1].charAt(0));
            boolean flag2=Character.isDigit(str2[1].charAt(0));
            if(!flag1&&!flag2){
                int tmp=str1[1].compareTo(str2[1]);
                if(tmp!=0){
                    return tmp;
                }
                return str1[0].compareTo(str2[0]);
            }
            return flag1?(flag2?0:1):-1;
        });
        return logs;
    }
}
